package com.Algorithm.HUAWEI.three20220323;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/04/08/14:50
 * @Description:
 * @Target:
 */
public class 计算字符串的编辑距离 {
    /*
    * Levenshtein 距离，又称编辑距离，指的是两个字符串之间，
    * 由一个转换成另一个所需的最少编辑操作次数。
    * 许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
    * 编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。

    例如：

    字符串A: abcdefg

    字符串B: abcdef

    通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

    要求：

    给定任意两个字符串，写出一个算法计算它们的编辑距离。


    数据范围：给定的字符串长度满足 1≤len(str)≤1000


    输入描述：
    每组用例一共2行，为输入的两个字符串

    输出描述：
    每组用例输出一行，代表字符串的距离

    示例1
    输入：
    abcdefg
    abcdef
    复制
    输出：
    1

    *
    *
    * */


    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String ss1 = in.readLine();
        String ss2 = in.readLine();
        System.out.println(ss1.length());
        System.out.println(ss2.length());
        System.out.println(dp(ss1,ss2));
        // Math.max(ss1.length(),ss2.length())-
    }



    static int dp(String ss1,String ss2){
        int[] ints1 = new int[ss2.length()+1];
        int[] ints2 = new int[ss2.length()+1];

        for (int i = 1; i < ints1.length; i++) {
            ints1[i] = i-1;
            ints2[i] = i-1;

        }

        for (int i = 0; i < ss1.length(); i++) {
            ints1[1] = i;
            for (int j = 0; j < ss2.length(); j++) {
                if (ss1.charAt(i) == ss2.charAt(j)) {
                    ints1[j+1] = ints2[j];
                }else {
                    ints1[j+1] = Math.min(ints2[j]+1, Math.min(ints1[j]+1,ints2[j+1]+1));
                }
            }


            for (int j = 0; j < ints2.length; j++) {
                ints2[j] = ints1[j];
                ints1[j] = 0;
            }
        }

         return ints2[ss2.length()];
    }
}
